GATE CSE 2002
Q3.
Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values : (1) Choose an i uniformly at random from [1....n] (2) If A[i] = x then stop else Goto 1; Assuming that x is present A, What is the expected number of comparisons made by the algorithm before it terminates?Q4.
Consider the following declaration of a two-dimensional array in C : Char a[100][100] Assuming that the main memory is byte-addressable and that array is stored starting form memory address 0, the address of a [40] [50] isQ5.
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the let sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following ?Q8.
Consider the following multiplexor where I0,I1,I2,I3 are four data input lines selected by two address line combinations A1A0 = 00,01,10,11 respectively and f is the output of the multiplexor. EN is the Enable input. The function f (x,y,z) implemented by the above circuit isQ9.
A device employing INTR line for device interrupt puts the CALL instruction on the data bus whileQ10.
In the worst case, the number of comparisons needed to search a single linked list of length n for a given element is